1. Field of the Invention
This invention relates to computer networks and, more specifically, to reconfiguring a computer network.
2. Background Information
Many organizations, including businesses, governments and educational institutions, utilize computer networks so that employees and others may share and exchange information and/or resources. A computer network typically comprises a plurality of entities interconnected by means of one or more communications media. An entity may consist of any device, such as a computer, that “sources” (i.e., transmits) or “sinks” (i.e., receives) data frames over the communications media. A common type of computer network is a local area network (“LAN”) which typically refers to a privately owned network within a single building or campus. LANs typically employ a data communication is protocol (LAN standard), such as Ethernet, FDDI, Wireless Fidelity (Wi-Fi) or token ring that defines the functions performed by data link and physical layers of a communications architecture (i.e., a protocol stack).
Spanning Tree Algorithm
Most computer networks include redundant communications paths so that a failure of any given link does not isolate any portion of the network. Such networks are typically referred to as meshed or partially meshed networks. The existence of redundant links, however, may cause the formation of circuitous paths or “loops” within the network. Loops are highly undesirable because data frames may traverse the loops indefinitely.
Furthermore, some devices, such as bridges or switches, replicate frames whose destination is not known resulting in a proliferation of data frames along loops. The resulting traffic can overwhelm the network. Other intermediate devices, such as routers, that operate at higher layers within the protocol stack, such as the Internetwork Layer of the Transmission Control Protocol/Internet Protocol (“TCP/IP”) reference model, deliver data frames and learn the addresses of entities on the network differently than most bridges or switches, such that routers are generally not susceptible to sustained looping problems.
To avoid the formation of loops, most bridges and switches execute a spanning tree protocol which allows them to calculate an active network topology that is loop-free (i.e., a tree) and yet connects every pair of LANs within the network (i.e., the tree is spanning). The IEEE has promulgated a standard (IEEE Std. 802.1D-1998™) that defines a spanning tree protocol to be executed by 802.1D compatible devices. In general, by executing the 802.1D spanning tree protocol, bridges elect a single bridge within the bridged network to be the “Root Bridge”. The 802.1D standard takes advantage of the fact that each bridge has a unique numerical identifier (bridge ID) by specifying that the Root Bridge is the bridge with the lowest bridge ID. In addition, for each LAN coupled to any bridge, exactly one port (the “Designated Port”) on one bridge (the “Designated Bridge”) is elected. The Designated Bridge is typically the one closest to the Root Bridge. All ports on the Root Bridge are Designated Ports, and the Root Bridge is the Designated Bridge on all the LANs to which it has ports.
Each non-Root Bridge also selects one port from among its non-Designated Ports (its “Root Port”) which gives the lowest cost path to the Root Bridge. The Root Ports and Designate Ports are selected for inclusion in the active topology and are placed in a forwarding state so that data frames may be forwarded to and from these ports and thus onto the LANs interconnecting the bridges and end stations of the network. Ports not included within the active topology are placed in a blocking state. When a port is in the blocking state, data frames will not be forwarded to or received from the port. A network administrator may also exclude a port from the spanning tree by placing it in a disabled state.
To obtain the information necessary to run the spanning tree protocol, bridges exchange special messages called configuration bridge protocol data unit (BPDU) messages or simply BPDUs. BPDUs carry information, such as assumed root and lowest root path cost, used in computing the active topology. More specifically, upon start-up, each bridge initially assumes itself to be the Root Bridge and transmits BPDUs accordingly. Upon receipt of a BPDU from a neighboring device, its contents are examined and compared with similar information (e.g., assumed root and lowest root path cost) stored by the receiving bridge in memory. If the information from the received BPDU is “better” than the stored information, the bridge adopts the better information and uses it in the BPDUs that it sends (adding the cost associated with the receiving port to the root path cost) from its ports, other than the port on which the “better” information was received. Although BPDUs are not forwarded by bridges, the identifier of the Root Bridge is eventually propagated to and adopted by all bridges as described above, allowing them to select their Root Port and any Designated Port(s).
In order to adapt the active topology to changes and failures, the Root Bridge periodically (e.g., every hello time) transmits BPDUs. In response to receiving BPDUs on their Root Ports, bridges transmit their own BPDUs from their Designated Ports, if any. Thus, BPDUs are periodically propagated throughout the bridged network, confirming the active topology. As BPDU information is updated and/or timed-out and the active topology is calculated, ports may transition from the blocking state to the forwarding state and vice versa. That is, as a result of new BPDU information, a previously blocked port may learn that it should be in the forwarding state (e.g., it is now the Root Port or a Designated Port).
Rapid Spanning Tree Protocol
Recently, the IEEE promulgated a new standard (the 802.1w standard) that defines a rapid spanning tree protocol (RSTP) to be executed by otherwise 802.1D compatible devices. The RSTP similarly selects one bridge of a bridged network to be the root bridge and defines an active topology that provides complete connectivity among the LANs while severing any loops. Each individual port of each bridge is assigned a port role according to whether the port is to be part of the active topology. The port roles defined by the 802.1w standard include Root, Designated, Alternate and Backup. The bridge port offering the best, e.g., lowest cost, path to the root is assigned the Root Port Role. Each bridge port offering an alternative, e.g., higher cost, path to the root is assigned the Alternate Port Role. Each bridge port providing the lowest cost path from a given LAN is assigned the Designated Port Role, while all other ports coupled to the given LAN in loop-back fashion are assigned the Backup Port Role.
Those ports that have been assigned the Root Port and Designated Port Roles are placed in the forwarding state, while ports assigned the Alternate and Backup Roles are placed in a discarding or blocking state. A port assigned the Root Port Role can be rapidly transitioned to the forwarding state provided that all of the ports assigned the Alternate Port Role are placed in the discarding or blocking state. Similarly, if a failure occurs on the port currently assigned the Root Port Role, a port assigned the Alternate Port Role can be reassigned to the Root Port Role and rapidly transitioned to the forwarding state, providing that the previous root port has been transitioned to the discarding or blocking state. A port assigned the Designated Port Role or a Backup Port that is to be reassigned to the Designated Port Role can be rapidly transitioned to the forwarding state, provided that the roles of the ports of the downstream bridge are consistent with this port being assigned the Designated Port Role. The RSTP provides an explicit handshake to be used by neighboring bridges to confirm that a new designated port can rapidly transition to the forwarding state.
Like the STP described in the 802.1D specification standard, bridges running RSTP also exchange BPDU messages in order to determine which roles to assign to the bridge's ports. The BPDU messages are also utilized in the handshake employed to rapidly transition designated ports to the forwarding state.
FIG. 1 is a block diagram of a RSTP BPDU message 100. The BPDU message 100 includes a BPDU message header 102 compatible with the Media Access Control (MAC) layer of the respective LAN standard. The message header 102 comprises a plurality of fields (not shown), such as a destination address (DA) field and a source address (SA) field. The DA field carries a unique bridge multicast destination address assigned to the spanning tree protocol. Appended to header 102 is a BPDU message area 104 that also contains a number of fields, including a protocol identifier (ID) field 106, a protocol version number field 108, a BPDU type field 110, a flags field 112, a root ID field 114, a root path cost field 116, a bridge ID field 118, a port ID field 120, a message age field 122, a maximum age field 124, a hello time field 126, and a forward delay field 128, among others. The root identifier field 114 typically contains the identifier of the bridge assumed to be the root and the bridge identifier field 118 contains the identifier of the bridge sourcing (i.e., sending) the BPDU 100. The root path cost field 116 contains a value representing the cost to reach the assumed root from the port on which the BPDU is sent, and the port identifier field 120 contains the identifying number of the port from which the BPDU is sent.
As shown, the flags field 112 carries a plurality of single or multiple bit flags that may be set, e.g., asserted, or cleared, e.g., de-asserted. Specifically, the flags field 112 includes a topology change flag 130, a proposal flag 132, a port role flag 134, a learning flag 136, a forwarding flag 138, an agreement flag 140 and a topology change acknowledgment (ACK) flag 142. The learning and forwarding flags 136 and 138 are set to reflect the current port state of the port from which the corresponding BPDU is being sent.
The handshake utilized by adjacent bridges for rapidly transitioning designated ports typically proceeds as follows. When an upstream bridge wishes to rapidly transition a designated port to the forwarding state, it issues a BPDU 100 from that port whose proposal flag 132 is asserted. The port role flag 134 is set to the value associated with the Designated Port Role. In the root ID and root path cost fields 114 and 116, the upstream bridge loads the corresponding information relative to the port from which the BPDU message 100 is to be sent. The upstream bridge then sends the BPDU message which is received at the neighboring downstream bridge.
Assuming the information contained in the BPDU message 100 is equal to or better than that currently stored by the port of the downstream bridge at which the BPDU is received, the downstream bridge asserts “sync” for all of its other bridge ports. Sync is a state machine variable defined by the 802.1w specification standard. Basically, this has the effect of causing the downstream bridge to transition all of its designated ports, other than “edge” ports, to the discarding state. An edge port is defined as a port which provides the only connection to a respective LAN, thereby representing an edge of the bridged network. Once the designated ports have been transitioned to the discarding state, the downstream bridge responds, typically through its root port, to the upstream bridge with a BPDU message 100 whose agreement flag 140 is asserted. This notifies the upstream bridge that the downstream bridge is in agreement with the upstream bridge's request to transition the respective port to the forwarding state.
In addition, the designated port(s) of the downstream bridge request permission from their downstream bridges to rapidly transition back to the forwarding state following the same process. That is, BPDU messages 100 with their proposal flags 132 asserted are sent from these ports. In effect, a “cut” is made in the active topology at the first affected designated port and the cut propagates down from this first designated port through all bridges on the subtree below it, i.e., in a direction away from the root, until the cut reaches the edge of the bridged network.
Virtual Local Area Networks
Is A computer network may also be segmented into a series of logical networks. For example, U.S. Pat. No. 5,394,402, issued Feb. 28, 1995 to Ross (the “'402 Patent”), discloses an arrangement for associating any port of a switch with any particular network segment. Specifically, according to the '402 patent, any number of physical ports of a particular switch may be associated with any number of groups within the switch by using a virtual local area network (VLAN) arrangement that virtually associates the port with a particular VLAN designation. More specifically, the switch or hub associates VLAN designations with its ports and further associates those VLAN designations with messages transmitted from any of the ports to which the VLAN designation has been assigned.
The VLAN designation for each port is stored in a memory portion of the switch such that every time a message is received on a given access port the VLAN designation for that port is associated with the message. Association is accomplished by a flow processing element which looks up the VLAN designation in the memory portion based on the particular access port at which the message was received. In many cases, it may be desirable to interconnect a plurality of these switches in order to extend the VLAN associations of ports in the network. Those entities having the same VLAN designation function as if they are all part of the same LAN. In order to preserve the boundaries of each VLAN, VLAN-aware bridges are specifically configured to prevent messages from being passed between parts of the network having different VLAN designations. Nonetheless, intermediate network devices operating above layer 2 (L2), such as routers, can relay messages between different VLAN segments.
In addition to the '402 patent, the IEEE promulgated a specification standard (IEEE Std. 802.1Q-1998) for Virtual Bridged Local Area Networks. To preserve VLAN associations of messages transported across trunks or links in VLAN-aware networks, both Ross and IEEE Std. 802.1Q-1998 disclose appending a VLAN identifier (VID) field to the corresponding frames. In addition, U.S. Pat. No. 5,742,604 to Edsall et al. (the “'604 patent”), which is commonly owned with the present application, discloses an Interswitch Link (ISL) encapsulation mechanism for efficiently transporting packets or frames, including VLAN-modified frames, between switches while maintaining the is VLAN association of the frames. In particular, an ISL link, which may utilize the Fast Ethernet standard, connects ISL interface circuitry disposed at each switch. The transmitting ISL circuitry encapsulates the frame being transported within an ISL header and ISL error detection information, while the ISL receiving circuitry strips off this information and recovers the original frame.
Multiple Spanning Tree Protocol
Recently, the IEEE published a supplement to IEEE Std. 802.1Q-1998 describing a Spanning Tree Protocol that is specifically designed for use with networks that support VLANs. The Multiple Spanning Tree Protocol (MSTP), which is identified as IEEE Std. 802.1s-2002, organizes a bridged network into regions. Within each region, MSTP establishes an Internal Spanning Tree (IST) which provides connectivity to all bridges within the respective region and to the ISTs established within other regions. The IST established within each MSTP Region also provides connectivity to the one Common Spanning Tree (CST) established outside of the MSTP regions by IEEE Std. 802.1Q-1998 compatible bridges running STP or RSTP. The IST of a given MST Region receives and sends BPDUs to the CST. Accordingly, all bridges of the bridged network are connected by a single Common and Internal Spanning Tree (CIST). From the point of view of the legacy or IEEE 802.1Q bridges, moreover, each MST Region appears as a single “virtual” bridge on the CST.
Within each MST Region, the MSTP compatible bridges establish a plurality of active topologies, each of which is called a Multiple Spanning Tree Instance (MSTI). The MSTP bridges also assign or map each VLAN to one and only one of the MSTIs. Because VLANs may be assigned to different MSTIs, frames associated with different VLANs can take different paths through an MSTP Region. The bridges may, but typically do not, compute a separate topology for every single VLAN, thereby conserving processor and memory resources. Each MSTI is basically a simple RSTP instance that exists only inside the respective Region, and the MSTIs do not interact outside of the Region.
MSTP also uses BPDUs to establish the ISTs and MSTIs as well as to define the boundaries of the different MSTP Regions. The bridges do not send separate BPDUs for each MSTI. Instead, every MSTP BPDU carries the information needed to compute the active topology for all of the MSTIs defined with the respective Region. Each MSTI, moreover, has a corresponding Identifier (ID) and the MSTI IDs are encoded into the bridge IDs. That is, each bridge has a unique ID, as described above, and this ID is made up of a fixed portion and a settable portion. With MSTP, the settable portion of a bridge's ID is further organized to include a system ID extension. The system ID extension corresponds to the MSTI ID. The MSTP compatible bridges within a given Region will thus have a different bridge ID for each MSTI. For a given MSTI, the bridge having the lowest bridge ID for that instance is elected the root. Thus, an MSTP compatible bridge may be the root for one MSTI but not another within a given MSTP Region.
Each bridge running MSTP also has a single MST Configuration Identifier (ID) that consists of three attributes: an alphanumeric configuration name, a revision level and a VLAN mapping table that associates each of the potential 4096 VLANs to a corresponding MSTI. Each bridge, moreover loads its MST Configuration ID into the BPDUs sourced by the bridge. Because bridges only need to know whether or not they are in the same MST Region, they do not propagate the actual table(s) mapping VLANs to MSTIs in their BPDUs. Instead, the MST BPDUs carry only a digest of the VLAN-to-MSTI mapping table(s). The digest is generated by applying the well-known MD-5 algorithm to the VLAN-to-MSTI mapping table(s). When a bridge receives an MST BPDU, it extracts the MST Configuration ID contained therein, including the digest, and compares it to its own MST Configuration ID to determine whether it is in the same MST Region as the bridge that sent the MST BPDU. If the two MST Configuration IDs are the same, then the two bridges are in the same MST Region. If, however, the two MST Configuration IDs have at least one non-matching attribute, i.e., either different configuration names, different revision levels and/or different computed digests, then the bridge that received the BPDU concludes that it is in a different MST Region than the bridge that sourced the BPDU. A port of an MST bridge, moreover, is considered to be at the boundary of an MST Region if the Designated Bridge is in a different MST Region or if the port receives legacy BPDUs.
FIG. 2 is a highly schematic block diagram of an MST BPDU 200. The MST BPDU 200 includes a header 202 compatible with the Media Access Control (MAC) layer of the respective LAN standard, e.g., Ethernet. The header 202 comprises a destination address (DA) field, a source address (SA) field, a Destination Service Access Point (DSAP) field, and a Source Service Access Point (SSAP), among others. The DA field 204 carries a unique bridge multicast destination address assigned to the spanning tree protocol, and the DSAP and SSAP fields carry standardized identifiers assigned to the spanning tree protocol. Appended to header 202 is a BPDU message area that includes an “outer” part 204 and an “inner” part 206. The outer part 204 has the same format as an RSTP BPDU message and is recognized as a valid RSTP BPDU message by bridges that do not implement MSTP. The “inner” part 206 is utilized by bridges executing MSTP to establish the IST and the MSTIs. The inner part 206 has a set of spanning tree parameters for the IST and a set of parameters for each MSTI supported by the bridge sourcing the MSTP BPDU 200.
Outer part 204, also referred to as the CIST priority vector, has a plurality of fields, including a protocol identifier (ID) field 208, a protocol version ID field 210, a BPDU type field 212, a flags field 214, a CIST root ID field 216, an external path cost field 218, a CIST regional root ID field 220, a CIST port ID field 222, a message age field 224, a maximum (MAX) age field 226, a hello time field 228, and a forward delay field 230. The flags field 214 of other part 204 includes the flags 130-142 (FIG. 1) described above in connection with the RSTP BPDU message format. The CIST root identifier field 216 contains the identifier of the bridge assumed to be the root of the Common and Internal Spanning Tree, which may be in the same MSTP Region as the bridge sourcing the BPDU message 200, in another MSTP Region or in part of the bridged network that is not running MSTP. The external path cost field 218 contains a value representing the lowest cost from the bridge sourcing the BPDU 200 to the CIST root identified in field 216 without passing through any other bridge in the same region as the bridge that is sourcing the BPDU message 200.
Inner part 206, also referred to as an MSTI priority vector, similarly has a plurality of fields, including a version 1 length field 232, a null field 234, a version 3 length field 236, an MST configuration ID field 238, a CIST regional root ID field 240, a CIST regional path cost field 242, a CIST bridge ID field 244, a CIST port ID field 246, a CIST flags field 248, and a CIST hops field 250. Inner part 206 may further include one or more optional MSTI configuration messages 252, each of which constitutes another MSTI priority vector or M-record.
Because version 2 of the RSTP does not specify any additional fields beyond those already specified by version 1, the MST BPDU does not have a version 2 length field.
Each MSTI Configuration Message 252 consists of a plurality of fields including a CIST regional root ID field 260, a CIST regional path cost field 262, a CIST bridge ID field 264, a CIST port ID field 266, a CIST flags field 268 and a CIST hops field 270. MST bridges utilize the STP parameters contained in fields 240-150 of inner part 206 and in each MSTI configuration message 252 to compute an active topology for each MSTI configured in the respective region.
Stack Arrangements
Multiple network devices, such as switches, may also be physically connected and logically organized to form a stack or cluster that can be made to appear to other entities or devices within the computer network at least logically as a single, virtual switch. One such technique involves forming a cascaded switch network by coupling multiple physical switches together via suitable bus connection links, such as Ethernet, Fast Ethernet, Fast EtherChannel®, Cisco GigaStack Gigabit Interface Converter (GBIC), Gigabit Ethernet, and Gigabit EtherChannel connections, among others (which may comprise additional circuitry), and programming the switches' internal control and forwarding circuitry, e.g., switch network management, bridge forwarding, etc., so as to permit the switches to operate as a single virtual switch. Examples of such clusters include the Catalyst Matrix™ from Cisco Systems, Inc.
The deployment of such stack or cluster designs within computer networks can affect the operation of the spanning tree protocol. Accordingly, a need exists for a technique that prevents loops while working efficiently with network devices organized into a stack or cluster.